#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>

using namespace std;

vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& q) {
    int n = heights.size();
    vector<int> ans(q.size(), -1);
    vector<vector<pair<int, int>>> qs(n);
    for (int i = 0; i < q.size(); i++)
    {
        int a = q[i][0], b = q[i][1];
        if (a > b)   swap(a, b);
        if (a == b || heights[a] < heights[b]) ans[i] = b;
        else    qs[b].emplace_back(heights[a], i);
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < n; i++)
    {
        while (pq.size() && pq.top().first < heights[i])
        {
            ans[pq.top().second] = i;
            pq.pop();
        }
        for (auto& p : qs[i])
            pq.emplace(p);
    }
    return ans;
}

void getcount(map<string, int>& m, string tmp, int num)
{
    string str;
    for (auto a : tmp)
    {
        if (isupper(a))
        {
            if (str.size())
            {
                m[str] += num;
                str.clear();
            }
            str.push_back(a);
        }
        else str.push_back(a);
    }
    if (str.size())
    {
        m[str] += num;
        str.clear();
    }
}

string countOfAtoms(string formula) {
    map<string, int> m;
    stack<int> stk;
    string s,num;
    int cnt = 1;
    for (int i = formula.size() - 1; i >= 0; i--)
    {
        char c = formula[i];
        if (isdigit(c)) {
            num = c + num;
        }
        else if (c == ')') {
            int t = num.size() ? stoi(num) : 1;
            num.clear();
            cnt *= t;
            stk.push(t);
        }
        else if (c == '(') {
            cnt /= stk.top();
            stk.pop();
        }
        else
        {
            s += c;
            if (isupper(c))
            {
                reverse(s.begin(), s.end());
                int t = num.size() ? stoi(num) : 1;
                m[s] += t * cnt;
                s.clear(), num.clear();
            }
        }
    }
    string ans;
    for (auto p : m)
    {
        ans.append(p.first);
        if (p.second > 1)    ans.append(to_string(p.second));
    }
    return ans;
}